#include <iostream>
#include<vector>
using namespace std;


class SeqList {//这个表里面的数据都是int
    private:
        int* data;       // 数组指针
        int maxSize;   // 顺序表的最大容量
        int length;    // 当前顺序表里面有几个元素
    public:
        SeqList(int size):maxSize(size) {
            data = new int[maxSize];//创建数组
            length = 0;
        }
        ~SeqList() {
            delete[] data;
        }

        int& operator[](int index) {// 重构运算符[]返回数组的元素
            return data[index];  
        }

        void printList(){
            for(int i=0;i<length;i++){
                cout<<data[i]<<", ";
            }
            cout<<endl;
        }

        // 插入元素
        bool insert(int element,int index=-1){
            if(index==-1){
                index=length;
            }
            if(length>=maxSize){
               cout<<"顺序存储结构满了\n";
               return false; 
            }
            if(index<-1||index>=maxSize){
                cout<<"不能在"<<index<<"位置插入\n";
                return false;
            }
            //开始移动了
            for(int i=length;i>index;i--){
                data[i]=data[i-1];
            }
            data[index]=element;
            ++length;
            return true;
        }
        //删除元素
        bool remove(int index=-1){
            if(index<0||index>=length){
                cout<<"index输入有误";
            }
            for(int i=index;i<length-1;i++){
                data[i]=data[i+1];
            }
            length--;
            return true;
        }
        int len() const{//输出长度
            return length;
        }
        //(1) 删除给定元素的算法。
        bool remove_ele(int element) {
            int index = -1;
            // 查找元素
            int mylist[length];//若有多个也可以删除
            int k=-1;
            for (int i = 0; i < length; ++i) {
                if (data[i] == element) {
                    k++;
                    mylist[k]=i;
                    
                }
            }
            // 如果没有找到，返回false
            if (k == -1) {
                cout << "没有找到该元素\n";
                return false;
            }
            // 删除元素并向前移动其他元素
            while(k>=0){
                remove(mylist[k]);
                k--;
            }
            return true;
        }
        //(2) 对于已排好序的线性表，删除所有重复元素的算法。
        bool remove_duplicates() {
            if (length < 2) return true; // 如果长度小于2，无需操作
            int j = 0;  // j是去重后的索引
            for (int i = 1; i < length; ++i) {
                if (data[i] != data[j]) {
                    j++;
                    data[j] = data[i];
                }
            }
            length = j + 1;  // 更新去重后的长度
            return true;
        }
        //(3) 线性表“逆置”算法。
        void reverse() {
            for (int i = 0; i < length / 2; ++i) {
                int temp = data[i];
                data[i] = data[length - 1 - i];
                data[length - 1 - i] = temp;
            }
        }
        //逆转区间，方便左右移动
        void reverse_segment(int start, int end) {
            while (start < end) {
                int temp = data[start];
                data[start] = data[end];
                data[end] = temp;
                ++start;
                --end;
            }
        }
        // (4) 线性表循环左移/右移 k 位的算法。
        // 循环左移 k 位
        void left_rotate(int k) {
            k = k % length;  // 防止 k 大于 length实际上是等效的
            reverse_segment(0, k - 1);       // 逆置前k个元素
            reverse_segment(k, length - 1);  // 逆置剩下的元素
            reverse();                       // 逆置整个数组
        }

        // 循环右移 k 位
        void right_rotate(int k) {
            left_rotate(length - k);  // 循环右移 k 位等价于左移 length - k 位
        }

        // (5) 合并两个已排好序的线性表的算法。
        SeqList merge(const SeqList& other) {
            SeqList result(maxSize + other.maxSize);  // 新表的大小为两个表大小之和
            int i = 0, j = 0, k = 0;
    
            // 依次合并
            while (i < length && j < other.length) {
                if (data[i] < other.data[j]) {
                    result.data[k++] = data[i++];
                } 
                else {
                    result.data[k++] = other.data[j++];
                }
            }

            // 将剩余元素加入结果中，不可能两个都剩余
            while (i < length) {
                result.data[k++] = data[i++];
            }
            while (j < other.length) {
                result.data[k++] = other.data[j++];
            }

            result.length = k;
            return result;
        }
};




int main(){
    SeqList a(20);
    a.insert(1);
    a.insert(1);
    a.insert(2);
    a.insert(2);
    a.insert(3);
    a.insert(4);
    a.insert(4);
    cout<<"最开始的数组: ";
    a.printList();
    
    a.remove_ele(1);
    cout<<"(1)删除1之后: ";
    a.printList();

    a.remove_duplicates();
    cout<<"(2) 对于已排好序的线性表，删除所有重复元素的算法:";
    a.printList();

    a.reverse();
    cout<<"(3) 线性表“逆置”算法：";
    a.printList();

    a.left_rotate(1);
    cout<<"(4) 线性表循环左移 1 位的算法: ";
    a.printList();

    a.right_rotate(1);
    cout<<"(4) 线性表循环右移 1 位的算法: ";
    a.printList();

    cout<<"(5) 合并两个已排好序的线性表的算法："<<endl;
    SeqList b(20);
    SeqList c(20);
    b.insert(0);
    b.insert(2);
    b.insert(4);
    c.insert(1);
    c.insert(3);
    c.insert(5);
    cout<<"第一个: ";
    b.printList();
    cout<<"第二个: ";
    c.printList();
    cout<<"合并后: ";
    b.merge(c).printList();
    return 0;
}